import java.util.Arrays;
//77
class Solution {
    private List<List<Integer>> ans = new ArrayList();
    private List<Integer> path = new ArrayList();
    private void dfs(int i, int n, int k){
        if(path.size() == k){
            ans.add(new ArrayList(path));
            return;
        }
        for(int j=i; j<=n; j++){
            path.add(j);
            dfs(j+1,n,k);
            path.remove(path.size()-1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        dfs(1,n,k);
        return ans;
    }
}
//513
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        List<TreeNode> cur = new ArrayList();
        cur.add(root);
        int ans = Integer.MAX_VALUE;
        while(!cur.isEmpty()){
            List<TreeNode> nxt = new ArrayList();
            List<Integer> vals = new ArrayList();
            for(TreeNode node : cur){
                if(node.left != null) nxt.add(node.left);
                if(node.right != null) nxt.add(node.right);
                vals.add(node.val);
            }
            ans = vals.get(0);
            cur = nxt;
        }
        return ans;
    }
}
//103
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList();
        if(root == null) return ans;
        List<TreeNode> cur = new ArrayList();
        cur.add(root);
        boolean flag = false;
        while(cur.size() != 0){
            List<TreeNode> nxt = new ArrayList();
            List<Integer> value = new ArrayList();
            for(int i=0; i<cur.size(); i++){
                TreeNode node = cur.get(i);
                if(node.left != null) nxt.add(node.left);
                if(node.right != null) nxt.add(node.right);
                value.add(node.val);
            }
            if(flag){
                Collections.reverse(value);
            }
            flag = !flag;
            ans.add(value);
            cur = nxt;
        }
        return ans;
    }
}
//102 - 层序遍历
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList();
        if(root == null){
            return ans;
        }
        List<TreeNode> cur = new ArrayList();
        cur.add(root);
        while(cur.size() != 0){
            List<TreeNode> nxt = new ArrayList();
            List<Integer> value = new ArrayList();
            for(int i=0; i<cur.size(); i++){
                TreeNode node = cur.get(i);
                if(node.left != null) nxt.add(node.left);
                if(node.right != null) nxt.add(node.right);
                value.add(node.val);
            }
            cur = nxt;
            ans.add(value);
        }
        return ans;
    }
}
class Solution {
    public String truncateSentence(String s, int k) {
        String[] ans = s.split(" ");
        String tmp = ans[0];
        for(int i=1; i<k; i++){
            tmp += " " + ans[i];
        }
        return tmp;
    }
}